#include "util.h"
#include "Const.h"
#include "Symbol.h"
#include <strings.h>

#define MAXNODES 20

namespace R{

struct pattern_t{
	char index;
	char next;
	char next_offset;
};

struct Tree{
	int nb;
	int index;
	char letter;
	bool term;
	Tree *nodes[MAXNODES];
	pattern_t *start;

	Tree(char l){
		nb = 0;
		letter = l;
		term = false;
		index = -1;
		memset(nodes, 0, MAXNODES*sizeof(Tree*));
	}

	void init(char l){
		letter = l;
		term = false;
		index = -1;
	}

	int insert(char *word, int idx){
		if(!*word){
			term = true;
			index = idx;
			return 0;
		}
		for(int i = 0; i < nb; i++)
			if(nodes[i]->letter == *word){
				return nodes[i]->insert(++word, idx);
			}
		rerror_on(nb > MAXNODES, "Cannot built argument matcher, more than %d (this constant may be increased)", MAXNODES);
		if(nodes[nb]){
			nodes[nb++]->init(*word);
		} else
			nodes[nb++] = new Tree(*word);
		return nodes[nb - 1]->insert(++word, idx) + 1;
	}

	void display(){
		for(int i = 0; i < nb; i++)
			nodes[i]->display(this);
	}

	void display(Tree *p){
		rprintf("n%p [ label=\"%d\" color=\"%s\"] ;\n", this, index, (index >= 0) ? "red": "blue");
		rprintf("n%p -> n%p [label=\"%c\"]; \n", p, this, letter);
		display();
	}

	int flattern(pattern_t** buff, int pos){
		int mark = -1;

		start = *buff; // Save current position in the buffer
		(*buff) += nb + (term ? 0 : 1); // Add an extra space for $ iff it's not already a $
																		// has to be kept in sync with the last test of this fun

		// Process childs to have positions
		for(int i = 0; i < nb ; i++){
			int nmark = nodes[i]->flattern(buff, 0);
			if(nb == 1) //propagate marker
				mark = nmark;
		}

		if((index < 0)) // Check for a last conflict (included word)
			index = mark;
		else if(nb == 0)
			mark = index;

		for(int i = 0; i < nb ; i++){
			Tree *node = nodes[i];
			start[i].next = node->letter;
			start[i].index = node->index;
			if(node->term && !node->nb){
				start[i].next_offset = 0; // It's a terminal node thus it points to nothing
			}else{
				start[i].next_offset = (node->start - start - i); // Compute the next index
			}
		}

		// Add a sentinel
		if(!term){ // avoiding to add an extra sentinel when it's already one
			start[nb].index = -1;
			start[nb].next = 0;
			start[nb].next_offset = -1;
		}
		return mark;
	}

	void reset(){
		for(int i = 0; i < nb; i++)
			nodes[i]->reset();
		nb = 0;
	}
};

struct R::pattern_t *build_pattern(int total, ConstPool *cpool, struct cpool_vector patterns){
	pattern_t result[100]; // A buffer
	pattern_t *tmp = &result[0]; // A pointer to the buffer

	static Tree *root = new Tree(0); // The root
	root->reset();
	for(int i = 0; i < total; i ++){ // Insert all names
		//printf("inserting %d (%d)", i, total);
		//(*cpool)[patterns.values[i]]->print();
		//printf("\n");
		//printf("--%s--\n", static_cast<Symbol*>((*cpool)[patterns.values[i]])->text);
		root->insert(static_cast<Symbol*>((*cpool)[patterns.values[i]])->text, i);
	}
	//printf("fun ok\n");
	root->flattern(&tmp, 0);
	//printf("flattern ok\n");

// 	rprintf("digraph G {\n");
// 	root->display();
// 	rprintf("}\n");

	// Return a copy
	return (pattern_t*)memcpy(new pattern_t[tmp - &result[0]],
			result, sizeof(pattern_t)*(tmp - &result[0]));
}

int match_pattern(char *input, pattern_t *pattern){
	int idx = -1;
	char n = pattern->next; // Whatever but 0 ... maybe use as a do { } while instead
	char c = *input;

	while(c && n){
		if(c == n){
			c = *(++input);
			idx = pattern->index;
			pattern += pattern->next_offset;
		} else
			pattern ++;
		n = pattern->next;
	}
	return idx;
}

};
